package tsp;

import java.util.ArrayList;

public class TSP_Heuristic {

    private double[][] coutsCycle;
    private double[][] coutsAffectation;
    private int nbSommets;
    private int alpha;
    private ArrayList<Integer> cycle;
    private int[] affectation; /* indice : pour un sommet donné hors cycle,
    valeur : le sommet auquel il est rataché */

    private ArrayList<Integer> cycleInitial;
    private int[] affectationInitiale;
    private final double lambdaListe[] = new double[]{0.1, 0.3, 0.5, 0.7, 0.9};
    private int coutSolution;
    private int coutSolutionInitiale;
    private long temps;
    private TSP_Solution solutionRetenue;

    public TSP_Heuristic(TSP_Data data, boolean withAllAlpha) {
        this.coutsAffectation = data.getCoutsAffectation();
        this.coutsCycle = data.getCoutsCycle();
        this.nbSommets = data.getNbSommets();
        this.alpha = data.getAlpha();

        cycle = new ArrayList<Integer>();
        affectation = new int[nbSommets];

        genererSolutionInitiale();

        coutSolution = calculerCoutSolution();
        coutSolutionInitiale = coutSolution;

        //System.out.println("\n=== CYCLE INITIAL ===");
        //System.out.println(cycle + " avec un coût de " + coutSolution);

        long before = System.currentTimeMillis();

        if (withAllAlpha) {
            calculerMeilleureSolution();
        } else {
            solutionRetenue = calculerHeuristique(0.5);
        }

        temps = System.currentTimeMillis() - before;
    }


    public TSP_Heuristic(TSP_Data data, boolean withAllAlpha, ArrayList<Integer> cycleInit) {
        this.coutsAffectation = data.getCoutsAffectation();
        this.coutsCycle = data.getCoutsCycle();
        this.nbSommets = data.getNbSommets();
        this.alpha = data.getAlpha();

        cycle = new ArrayList<Integer>();
        affectation = new int[nbSommets];

        cycle = cycleInit;

        calculerAffectations();

        cycleInitial = (ArrayList<Integer>) cycle.clone();
        affectationInitiale = affectation.clone();

        coutSolution = calculerCoutSolution();
        coutSolutionInitiale = coutSolution;

        //System.out.println("\n=== CYCLE INITIAL ===");
        //System.out.println(cycle + " avec un coût de " + coutSolution);

        long before = System.currentTimeMillis();

        if (withAllAlpha) {
            calculerMeilleureSolution();
        } else {
            solutionRetenue = calculerHeuristique(0.5);
        }

        temps = System.currentTimeMillis() - before;
    }

    /**
     * Génère un cycle initial de 3 sommets dont 2 aléatoires
     * ainsi que les affectations correspondantes pour les sommets restants
     */
    private void genererSolutionInitiale() {
        /* Deuxième et troisième sommets choisis aléatoirement
        parmi tous les sommets excepté le premier */
        int sommet0 = 0;
        int sommet1 = (int) (Math.random() * (nbSommets - 1)) + 1;
        int sommet2;

        do {
            sommet2 = (int) (Math.random() * (nbSommets - 1)) + 1;
        } while (sommet1 == sommet2);

        cycle.add(sommet0);
        cycle.add(sommet1);
        cycle.add(sommet2);

        calculerAffectations();

        cycleInitial = (ArrayList<Integer>) cycle.clone();
        affectationInitiale = affectation.clone();
    }

    public void reinitialiserSolution() {
        cycle = (ArrayList<Integer>) cycleInitial.clone();
        affectation = affectationInitiale.clone();
        coutSolution = coutSolutionInitiale;
    }

    /**
     * Appelle l'heuristique pour chaque lambda et choisit la meilleure solution
     * en terme de cout total
     */
    private void calculerMeilleureSolution() {
        TSP_Solution solutionCourante;
        solutionRetenue = new TSP_Solution();

        //System.out.print("\n=== COUTS DES SOLUTIONS EN FONCTION DE LAMBDA ===\n");
        for (double lambda : lambdaListe) {

            solutionCourante = calculerHeuristique(lambda);

            //System.out.println("Lambda=" + solutionCourante.getLambda()
            //        + " ==> cout solution=" + solutionCourante.getCoutSolution());

            if (solutionCourante.getCoutSolution() < solutionRetenue.getCoutSolution()) {
                solutionRetenue = solutionCourante;
            }
        }
    }

    /**
     * Calcule l'heuristique : pour chaque sommet hors cycle, savoir
     * lequel est le meilleur en terme d'optimisation du coût total de la solution
     * si on vient à l'ajouter. Ajouter ces meilleurs sommets au cycle jusqu'à
     * ce qu'on ne trouve plus de solution améliorante.
     */
    private TSP_Solution calculerHeuristique(double lambda) {
        double Ls, L;
        double inc, dec, incOptimal, decOptimal;
        int sommetRetenu, sommetPrecedent; //sommet retenu à insérer avant sommetSuivant

        /* Réinitialisation à la solution initiale */
        reinitialiserSolution();

        do {
            L = 0;
            sommetRetenu = -1;
            sommetPrecedent = -1;
            incOptimal = 0;
            decOptimal = 0;

            //Pour chaque sommet s hors cycle
            for (int s = 0; s < nbSommets; s++) {
                if (horsCycle(s)) {
                    Ls = 0;

                    dec = calculerDec(s);

                    /* Pour chaque arc du cycle, calculer l'incrémentation du cout
                     * du cycle puis la décrémentation du cout des affectations
                    que provoquerait l'insertion de s */
                    for (int sommetCycle : cycle) {
                        //calculer si on insère s après sommetCycle
                        inc = calculerInc(s, sommetCycle);

                        Ls = lambda * inc + (1 - lambda) * (-dec);

                        if (Ls < L) {
                            L = Ls;
                            incOptimal = inc;
                            decOptimal = dec;
                            sommetRetenu = s;
                            sommetPrecedent = sommetCycle;
                        }
                    }

                }
            }

            //Si le sommet permet d'améliorer la solution, alors l'ajouter
            if (L < 0) {
                ajouterSommetAuCycle(sommetRetenu, sommetPrecedent);
                coutSolution += incOptimal - decOptimal;
            }

        } while (L < 0); //Tant qu'on trouve une solution améliorante

        return new TSP_Solution(cycle, affectation, lambda, alpha, coutSolution);
    }

    /**
     * Calcule l'incrémentation du coût du cycle que pourrait provoquer
     * l'ajout de s au cycle entre sommetCycle et son successeur
     * @param s le sommet à ajouter au cycle
     * @param sommetCycle le sommet prédécesseur de s
     * @return l'incrémentation
     */
    private double calculerInc(int s, int sommetCycle) {
        int precedent = sommetCycle;
        int suivant = trouverSommetSuivant(sommetCycle);

        //Si on insère C entre arc AB : inc = cout(A, C) + cout(C, B) - cout(A, B)
        return coutsCycle[precedent][s] + coutsCycle[s][suivant] - coutsCycle[precedent][suivant];
    }

    /**
     * Calcule la décrémentation du coût des affectations que pourrait provoquer
     * l'ajout de s dans le cycle
     * @param s le sommet ajouté au cycle
     * @return la décrémentation
     */
    private double calculerDec(int s) {
        double coutActuel, coutEventuel;
        double dec;

        //1- Retirer le cout d'affectation entre s et et son sommet cycle
        dec = coutsAffectation[s][affectation[s]];

        //Pour chaque sommet hors cycle et hors sommet s
        for (int i = 0; i < nbSommets; i++) {
            if (horsCycle(i) && i != s) {
                coutActuel = coutsAffectation[i][affectation[i]];
                coutEventuel = coutsAffectation[i][s];

                if (coutEventuel < coutActuel) {
                    dec += coutActuel - coutEventuel;
                }
            }
        }

        return dec;
    }

    /**
     * Trouve le sommet successeur d'un sommet donné
     * @param s le sommet à partir duquel on recherche le suivant
     * @return le successeur de s
     */
    private int trouverSommetSuivant(int s) {
        //Si le soommet est le dernier élément du cycle, alors le suivant
        //est le premier élément de la liste
        if (cycle.indexOf(s) == cycle.size() - 1) {
            return cycle.get(0);
        } else {
            return cycle.get(cycle.indexOf(s) + 1);
        }
    }

    /**
     * Affecte chaque sommet hors cycle à un sommet du cycle, le plus proche
     */
    private void calculerAffectations() {
        /* Affecter les sommets restants aux sommets du cycle généré */
        for (int i = 0; i < nbSommets; i++) {
            //Pour chaque sommet hors cycle, trouver le sommet du cycle
            //le plus proche
            if (horsCycle(i)) {
                affectation[i] = trouverPlusProcheSommet(i);
            } else {
                affectation[i] = -1;
            }
        }
    }

    /**
     * Teste si un sommet donné n'appartient pas au cycle de la solution
     * @param s le sommet à tester
     * @return vrai si le sommet est hors cycle (affecté, false sinon
     */
    private boolean horsCycle(int s) {
        return !cycle.contains(s);
    }

    /**
     * Pour un sommet hors cycle donné s, trouve le sommet du cycle le plus proche
     * auquel s doit être affecté
     * @param s le sommet testé
     * @return le sommet le plus proche de s ou -1 si aucun sommet dans le cycle
     */
    private int trouverPlusProcheSommet(int s) {
        int plusProche = -1;
        double coutAffectation = Double.MAX_VALUE;

        //s ne doit pas être un sommet du cycle évidemment...
        if (cycle.contains(s)) {
            return -1;
        }

        //Tester tous les sommets du cycle
        for (int sommetCycle : cycle) {
            //Si on trouve plus proche que le sommet précédent
            if (coutsAffectation[s][sommetCycle] < coutAffectation) {
                plusProche = sommetCycle;
                coutAffectation = coutsAffectation[s][sommetCycle];
            }
        }

        return plusProche;
    }

    /**
     * Ajoute un sommet s au cycle, après sommetPrecedent
     * @param s le sommet à ajouter au cycle
     * @param sommetPrecedent le sommet qui devient le prédécesseur de s
     */
    private void ajouterSommetAuCycle(int s, int sommetPrecedent) {
        /* 1- Ajout au cycle */
        cycle.add(cycle.indexOf(sommetPrecedent) + 1, s);

        /* 2- Recalculer les affectations */
        calculerAffectations();
    }

    /**
     * Calcule le cout total de la solution (cycle + affectations)
     * @return le cout de la solution
     */
    private int calculerCoutSolution() {
        int coutCycle = 0;
        int coutAffectations = 0;

        /* 1- Calcul de la somme des couts des arcs du cycle */
        int sommetCycle, sommetCycleSuivant;

        for (int i = 0; i < cycle.size(); i++) {
            sommetCycle = cycle.get(i);

            //Si on a atteint le bout de la liste c'est que le suivant
            //est le sommet initial du cycle
            sommetCycleSuivant = trouverSommetSuivant(sommetCycle);

            //Cumuler le cout de l'arc au cout total
            coutCycle += coutsCycle[sommetCycle][sommetCycleSuivant];
        }

        /* 2- Calcul de la somme des couts des arcs des affectations */
        for (int s = 0; s < nbSommets; s++) {
            //on ne traite que les sommets hors cycle
            if (horsCycle(s)) {
                coutAffectations += coutsAffectation[s][affectation[s]];
            }
        }

        coutSolution = coutCycle + coutAffectations;
        return coutSolution;
    }

    public TSP_Solution getSolutionRetenue() {
        return solutionRetenue;
    }

    /**
     * Retourne le temps d'exécution de l'heuristique
     */
    public long getTempsHeuristique() {
        return temps;
    }
}
